package probabilities;

import java.util.ArrayList;
import java.util.List;
import java.util.HashMap;
import java.util.TreeMap;
import java.util.Map;


public class Probabilities {
    
    // A list used by getPatternsList() function to store all possible patterns of required length.
    // It cannot be declared inside the getPatternsList() function as it is recursive. 
    private List<String> consideredPatterns = new ArrayList<String>();
    
    // This function calculates the probability of one pattern to happen before another.
    public Map<String, Double> getProbabilities(String pattern1, String pattern2) {
        
        // Define pattern length.
        int n = pattern1.length();
        
        HashMap<String, Double> nextPatterns = new HashMap<String, Double>();         
        HashMap<String, Double > currentPatterns = new HashMap<String, Double>();
                     
        // Get all possible patterns of required length.
        consideredPatterns.clear();
        getPatternsList("HT", n, new StringBuffer());
         
        // Define all patterns that are different from these taken by the function.
        consideredPatterns.remove(pattern1);
        consideredPatterns.remove(pattern2);
        
        // To simplify calculations each pattern is given a probability value equal to one.
        // Later that will be divided by a number of all possible patterns to make the whole probability space to be equal to 1.
        // This doesn't exclude patterns taken by the function.
        double pattern1Wins = 1;
        double pattern2Wins = 1;
        
        // First loop examines all sequences that are different from patterns taken by the function 
        for (int i=0; i < consideredPatterns.size(); i++) {
            
            // All of the patterns that are different from these taken by the function are given a probability value equal to one.
            currentPatterns.put(consideredPatterns.get(i), 1.00);
        
            double pattern1WinsLocal = 0;
            double pattern2WinsLocal = 0;
            
            //Define a value that is handed when a pattern goes back to some stage of its path.
            Map<String, Double> addedValues = new HashMap<String, Double>();       
            addedValues.put(consideredPatterns.get(i), 0.00);           
            
            // Second loop runs until required accuracy is achieved.
            int noOfCycles = 0;
            while (pattern1WinsLocal+pattern2WinsLocal<0.99995) {
                
                noOfCycles = noOfCycles+1;                
                if (currentPatterns.isEmpty()) {               
                    currentPatterns.put(consideredPatterns.get(i), addedValues.get(consideredPatterns.get(i)) );
                }
                
                //Third loop runs a whole cycle
                while(!currentPatterns.isEmpty()) {                    
                    
                    // Fourth loop runs for a single stage of a cycle.
                    for( int j=1; j<=currentPatterns.size(); j++) {
                        
                        String currentPattern = (String)currentPatterns.keySet().toArray()[j-1];
                        String currentPatternLastn = currentPattern.substring(currentPattern.length()-n, currentPattern.length());
                        
                        String appendT = currentPattern + "T";                        
                        String appendTLastn = appendT.substring(appendT.length()-n, appendT.length());
                                                
                        String appendH = currentPattern + "H";
                        String appendHLastn = appendH.substring(appendH.length()-n, appendH.length());
                        
                        double leftValue = currentPatterns.get(currentPattern);
                        
                        if (!addedValues.containsKey(appendT)) {
                            addedValues.put(appendT, 0.00);
                        }
                        
                        if (!addedValues.containsKey(appendH)) {
                            addedValues.put(appendH, 0.00);
                        }
                        
                        // Both patterns obtained after one more toss hit patterns taken by the function.
                        // Hand a half of the probability value of the examined pattern to each pattern taken by the function.
                        if (( appendTLastn.equals(pattern1) && appendHLastn.equals(pattern2) ) || 
                                ( appendTLastn.equals(pattern2) && appendHLastn.equals(pattern1) )) {
                            pattern1WinsLocal = pattern1WinsLocal + 0.5*leftValue;
                            pattern2WinsLocal = pattern2WinsLocal + 0.5*leftValue;                            
                        
                        // One of the patterns obtained after one more toss hits the first pattern taken by the function 
                        // while last n entries of the other pattern remain unchanged.
                        // Hand all the probability value of the examined pattern to the first pattern taken by the function.   
                        } else if (( appendTLastn.equals(pattern1) && appendHLastn.equals(currentPatternLastn) ) || 
                                ( appendTLastn.equals(currentPatternLastn) && appendHLastn.equals(pattern1) )) {
                            pattern1WinsLocal = pattern1WinsLocal + leftValue;                            
                        
                        // One of the patterns obtained after one more toss hits the second pattern taken by the function 
                        // while last n entries of the other pattern remain unchanged.
                        // Hand all the probability value of the examined pattern to the second pattern taken by the function.   
                        } else if (( appendTLastn.equals(pattern2) && appendHLastn.equals(currentPatternLastn) ) || 
                                ( appendTLastn.equals(currentPatternLastn) && appendHLastn.equals(pattern2) )) {
                            pattern2WinsLocal = pattern2WinsLocal + leftValue;                            
                        
                        /* A pattern obtained by appending tails hits the first pattern taken by the function 
                           while the other pattern obtained after one more toss goes back to some stage of the cycle.
                           Hand a half of the probability value of the examined pattern to the first pattern taken by the function
                           and another half of that value to a pattern returned by the function nextPatternsBefore 
                           applied to a pattern obtained by appending tails. */    
                        } else if (appendTLastn.equals(pattern1) && nextPatternsBefore(appendH, n)!=null) {
                            pattern1WinsLocal =pattern1WinsLocal +0.5*leftValue;
                            String goBack = nextPatternsBefore(appendH, n);
                            double newAddedValue = addedValues.get(goBack) + 0.5*leftValue;
                            addedValues.put(goBack, newAddedValue );                            
                        
                        /* A pattern obtained by appending heads hits the first pattern taken by the function 
                           while the other pattern obtained after one more toss goes back to some stage of the cycle.
                           Hand a half of the probability value of the examined pattern to the first pattern taken by the function
                           and another half of that value to a pattern returned by the function nextPatternsBefore 
                           applied to a pattern obtained by appending tails. */
                        } else if ( appendHLastn.equals(pattern1) && nextPatternsBefore(appendT, n)!=null ) {
                            pattern1WinsLocal = pattern1WinsLocal + 0.5*leftValue;
                            String goBack = nextPatternsBefore(appendT, n);
                            double newAddedValue = addedValues.get(goBack) + 0.5*leftValue; 
                            addedValues.put(goBack , newAddedValue);                            
                        
                        /* A pattern obtained by appending tails hits the second pattern taken by the function 
                           while the other pattern obtained after one more toss goes back to some stage of the cycle.
                           Hand a half of the probability value of the examined pattern to the second pattern taken by the function
                           and another half of that value to a pattern returned by the function nextPatternsBefore 
                           applied to a pattern obtained by appending heads. */    
                        } else if ( appendTLastn.equals(pattern2) && nextPatternsBefore(appendH, n)!=null ) {
                            pattern2WinsLocal = pattern2WinsLocal + 0.5*leftValue;
                            String goBack = nextPatternsBefore(appendH, n);
                            double newAddedValue = addedValues.get(goBack) + 0.5*leftValue; 
                            addedValues.put(goBack , newAddedValue); 
                        
                        /* A pattern obtained by appending heads hits the second pattern taken by the function 
                           while the other pattern obtained after one more toss goes back to some stage of the cycle.
                           Hand a half of the probability value of the examined pattern to the second pattern taken by the function
                           and another half of that value to a pattern returned by the function nextPatternsBefore 
                           applied to a pattern obtained by appending tails. */    
                        } else if ( appendHLastn.equals(pattern2) && nextPatternsBefore(appendT, n)!=null ) {
                            pattern2WinsLocal = pattern2WinsLocal + 0.5*leftValue;
                            String goBack = nextPatternsBefore(appendT, n);
                            double newAddedValue = addedValues.get(goBack) + 0.5*leftValue; 
                            addedValues.put(goBack , newAddedValue);                             
                        
                        /* A pattern obtained by appending tails goes back to some stage of the cycle. 
                           while last n entries of the other pattern obtained after one more toss remain unchanged.
                           Hand all the probability value of the examined pattern 
                           to a pattern returned by the function nextPatternsBefore applied to a pattern obtained by appending tails. */    
                        } else if ( nextPatternsBefore(appendT, n)!=null && appendHLastn.equals(currentPatternLastn) ) {
                            String goBack = nextPatternsBefore(appendT, n);
                            double newAddedValue = addedValues.get(goBack) + leftValue; 
                            addedValues.put(goBack , newAddedValue); 
                        
                        /* A pattern obtained by appending heads goes back to some stage of the cycle. 
                           while last n entries of the other pattern obtained after one more toss remain unchanged.
                           Hand all the probability value of the examined pattern 
                           to a pattern returned by the function nextPatternsBefore applied to a pattern obtained by appending heads. */ 
                        } else if ( appendTLastn.equals(currentPatternLastn) && nextPatternsBefore(appendH, n)!=null ) {
                            String goBack = nextPatternsBefore(appendH, n);
                            double newAddedValue = addedValues.get(goBack) + leftValue; 
                            addedValues.put(goBack , newAddedValue); 
                        
                        // Both patterns obtained after one more toss go back to some stage of the cycle.
                        // Hand all the probability value of the examined pattern to patterns obtained on earlier stages of the cycle.    
                        } else if ( nextPatternsBefore(appendT, n)!=null && nextPatternsBefore(appendH, n)!=null ) {
                            String goBackFirst = nextPatternsBefore(appendT, n);
                            double newAddedValueFirst = addedValues.get(goBackFirst) + 0.5*leftValue; 
                            addedValues.put(goBackFirst, newAddedValueFirst);
                            String goBackSecond = nextPatternsBefore(appendH, n);
                            double newAddedValueSecond = addedValues.get(goBackSecond) + 0.5*leftValue;
                            addedValues.put(goBackSecond, newAddedValueSecond );
                        
                        // A pattern obtained by appending tails hits the first pattern taken by the function. 
                        // Hand a half of the probability value of the examined pattern to the first pattern taken by the function
                        // nad another half of that value to a pattern obtained by appending heads.
                        } else if (appendTLastn.equals(pattern1)) {
                            pattern1WinsLocal = pattern1WinsLocal + 0.5*leftValue;
                            nextPatterns.put(appendH, leftValue*0.5 + addedValues.get(appendH));                            
                        
                        // A pattern obtained by appending tails hits the second pattern taken by the function.
                        // Hand a half of the probability value of the examined pattern to the second pattern taken by the function
                        // nad another half of that value to a pattern obtained by appending heads.    
                        } else if ( appendTLastn.equals(pattern2) ) {
                            pattern2WinsLocal = pattern2WinsLocal + 0.5*leftValue;
                            nextPatterns.put(appendH, leftValue*0.5 + addedValues.get(appendH));
                        
                        // A pattern obtained by appending heads hits the first pattern taken by the function.
                        // Hand a half of the probability value of the examined pattern to the first pattern taken by the function
                        // nad another half of that value to a pattern obtained by appending tails.    
                        } else if ( appendHLastn.equals(pattern1) ) {
                            pattern1WinsLocal = pattern1WinsLocal + 0.5*leftValue;
                            nextPatterns.put(appendT, leftValue*0.5 + addedValues.get(appendT));                            
                        
                        // A pattern obtained by appending heads hits the second pattern taken by the function.
                        // Hand a half of the probability value of the examined pattern to the second pattern taken by the function
                        // nad another half of that value to a pattern obtained by appending tails.    
                        } else if ( appendHLastn.equals(pattern2) ) {
                            pattern2WinsLocal = pattern2WinsLocal + 0.5*leftValue;
                            nextPatterns.put(appendT, leftValue*0.5 + addedValues.get(appendT));                            
                        
                        // Last n entries of a pattern obtained by appending tails remain unchanged.
                        // Hand all the probability value of the examined pattern to a pattern obtained by appending heads.    
                        } else if ( appendTLastn.equals(currentPatternLastn) ) {
                            nextPatterns.put(appendH, leftValue + addedValues.get(appendH));                            
                        
                        // Last n entries of a pattern obtained by appending heads remain unchanged.
                        // Hand all the probability value of the examined pattern to a pattern obtained by appending tails.      
                        } else if ( appendHLastn.equals(currentPatternLastn) ) {
                            nextPatterns.put(appendT, leftValue + addedValues.get(appendT));                            
                         
                        /* A pattern obtained by appending tails goes back to some stage of the cycle.
                           Hand a half of the probability value of the examined pattern to a pattern obtained by appending heads
                           and another half of that value to a pattern returned by the function nextPatternsBefore 
                           applied to a pattern obtained by appending tails. */       
                        } else if ( nextPatternsBefore(appendT, n)!=null ) {
                            String goBack = nextPatternsBefore(appendT, n);
                            double newAddedValue = addedValues.get(goBack) + 0.5*leftValue; 
                            addedValues.put(goBack , newAddedValue); 
                            nextPatterns.put(appendH, leftValue*0.5 + addedValues.get(appendH));                            
                         
                        /* A pattern obtained by appending heads goes back to some stage of the cycle. 
                           Hand a half of the probability value of the examined pattern to a pattern obtained by appending tails
                           and another half of that value to a pattern returned by the function nextPatternsBefore 
                           applied to a pattern obtained by appending heads. */  
                        } else if ( nextPatternsBefore(appendH, n)!=null ) {
                            String goBack = nextPatternsBefore(appendH, n);
                            double newAddedValue = addedValues.get(goBack) + 0.5*leftValue; 
                            addedValues.put(goBack , newAddedValue); 
                            nextPatterns.put(appendT, leftValue*0.5 + addedValues.get(appendT));                          
                        
                        // None of the above cases.    
                        // Hand all the probability value of the examined pattern to patterns obtained after one more toss.
                        } else /*if ( !append1Last3.equals(pattern1) &&
                                      !append0Last3.equals(pattern1) &&
                                      !append1Last3.equals(pattern2) &&
                                      !append0Last3.equals(pattern2) &&
                                      !append1Last3.equals(currentPatternLast3) &&
                                      !append0Last3.equals(currentPatternLast3) &&
                                      nextPatternsBefore(append1) == null &&
                                      nextPatternsBefore(append0) == null ) */
                        {
                            nextPatterns.put(appendT, leftValue*0.5 + addedValues.get(appendT));
                            nextPatterns.put(appendH, leftValue*0.5 + addedValues.get(appendH));                            
                        }
                        
                        // Cleare the probability value of the examined pattern. 
                        addedValues.put(currentPattern, 0.00);
                        
                    } 
                    
                    // Set patterns for the next stage of a cycle.
                    currentPatterns.clear();             
                    currentPatterns = (HashMap<String, Double >)nextPatterns.clone();       
                    nextPatterns.clear();
                    
                }
                
                // If statements evaluated after first completed cycle.
                // If entered these statements prevent the loop from running consecutive cycles. 
                if (noOfCycles==1) {
                    
                    // If after first cycle only one of the patterns taken by the function can be hit,
                    // we hand all the probability value of the examined pattern to the pattern that can be hit.
                    if (pattern1WinsLocal==0){
                        pattern2WinsLocal=1;
                        break;
                    } else if (pattern2WinsLocal==0) {
                        pattern1WinsLocal=1;
                        break;
                    }
                    
                    /* If after first cycle both of the patterns taken by the function can be hit 
                       but the examined pattern doesn't go back to any stage other then a beginning, 
                       we hand all the probability value of the examined pattern to both winning patterns 
                       proportionaly to what has been handed after first cycle. */
                    double sumOfAddedValues =0;
                    for (Double value : addedValues.values()) {                    
                        sumOfAddedValues = sumOfAddedValues + value;
                    }
                    if (sumOfAddedValues==0) {
                        pattern1WinsLocal = pattern1WinsLocal/(pattern1WinsLocal+pattern2WinsLocal);
                        pattern2WinsLocal = 1 - pattern1WinsLocal;
                        break;
                    }
                    
                }

                
            }   
            
            pattern1Wins = pattern1Wins + pattern1WinsLocal;
            pattern2Wins = pattern2Wins + pattern2WinsLocal;
            addedValues.clear();
            
        } 
        
        // Round numbers to 2 decimal places and express them as percentages.
        double pattern1WinsProbability = Math.round((pattern1Wins/(consideredPatterns.size()+2))*10000.0)/100.0;
        double pattern2WinsProbability = Math.round((pattern2Wins/(consideredPatterns.size()+2))*10000.0)/100.0;
        
        // Return a map of patterns and probabilities.
        Map<String, Double> result = new TreeMap<String, Double>();
	result.put(pattern1, pattern1WinsProbability);
	result.put(pattern2, pattern2WinsProbability);
        return result;
                
    }
    
    
    // Recursive function used to generate all patterns of required length.        
    private void getPatternsList(String input, int patternLength, StringBuffer output) {
            
        if (patternLength == 0) {
            consideredPatterns.add(output.toString());            
        } else {
            for (int i = 0; i < input.length(); i++) {
                output.append(input.charAt(i));
                getPatternsList(input, patternLength - 1, output);
                output.deleteCharAt(output.length() - 1);
            }
        } 
           
    }
    
    
    // This is a helper function that checks if a pattern goes back to some stage of a cycle.
    private static String nextPatternsBefore(String nextPatterns, int n) {
        String goBack = null;
        String nextPatternsLastn = nextPatterns.substring(nextPatterns.length()-n, nextPatterns.length());
        
        for( int k=n-1; k<=nextPatterns.length()-n && goBack==null; k++) {
            String previousPatterns = nextPatterns.substring( 0, nextPatterns.length()-k );
            String previousPatternsLastn = previousPatterns.substring(previousPatterns.length()-n, previousPatterns.length());
            if ( previousPatternsLastn.equals(nextPatternsLastn) ) {
                goBack = previousPatterns;
            }
        }
        return goBack;           
    }



}


